GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Entartung (Informatik)</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Entartung (Informatik)</span></h1>

</header>

</div>

<p>Eine <a href="Datenstruktur" title="Datenstruktur">Datenstruktur</a> wird als <b>entartet</b> bezeichnet, wenn sie final einen Zustand angenommen hat, in dem sie anders als vor der Entartung nachteilig wirkt. Dies kann aufgrund ungünstiger Eingabedaten geschehen.

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

<p>Eine grundlegende Datenstruktur sind sortierte <a href="Bin%C3%A4rbaum" title="Binärbaum">Binärbäume</a>. Diese bestehen aus Knoten mit jeweils zwei Nachfolgerknoten, wobei alle Knoten des linken Teilbaumes (= linker Nachfolgerknoten und dessen Nachfolger, auch die indirekten) kleiner und alle Knoten des rechten Teilbaumes größer als dieser sind:

</p>

<pre> [7]

/ \

[3] [12]

/ \ / \

[1] [4] [9] [15]

</pre>

<p>Was solche binären Bäume auszeichnet, ist, dass der Baum stets sortiert ist. Das Einfügen neuer Knoten hat die <a href="Komplexit%C3%A4tstheorie" title="Komplexitätstheorie">Komplexität</a> O(log(N)), im Gegensatz zu O(N) bei einer sortierten <a href="Liste_(Datenstruktur)" title="Liste (Datenstruktur)">Liste</a>.

</p><p>Kommen die Knoten beim Erstellen des Baumes jedoch in ungünstiger Reihenfolge, so kann eine Entartung des Baumes die Folge sein:

</p>

<pre>[1]

[3]

[4]

[7]

[9]

[12]

[15]

</pre>

<p>Jetzt ist der Baum zwar immer noch sortiert, der Aufwand des Einfügens neuer Knoten ist jedoch O(N), da er praktisch eine sortierte Liste ist.

</p>

<div class="mw-heading mw-heading2"><h2 id="Anfälligkeit"><span id="Anf.C3.A4lligkeit"></span>Anfälligkeit</h2></div>

<p>Viele gebräuchliche Datenstrukturen sind für Entartung anfällig, Beispiele hierfür sind der oben erwähnte sortierte binäre Baum und viele Implementierungen von <a href="Hash-Tabelle" class="mw-redirect" title="Hash-Tabelle">Hash-Tabellen</a> ohne Feedback.

</p><p>Je nach Datenstruktur ist die Anfälligkeit gegen Entartung verschieden. Bei obigem binären Baum reicht es aus, dass die Eingabedaten sortiert sind; bei determiniert oder stochastisch konfigurierten Hashtabellen und <i>vernünftigen</i> Hashfunktionen ist eine Entartung aber sehr unwahrscheinlich und wird deshalb meist vernachlässigt.

</p><p>Es gibt aber auch Datenstrukturen, die durch spezielle Maßnahmen gegen Entartung immun sind, z. B. <a href="Rot-Schwarz-Baum" title="Rot-Schwarz-Baum">Rot-Schwarz-Bäume</a>. Die Absicherung kostet in der Regel etwas Effizienz, erhöht dafür aber die <a href="Worst-Case" class="mw-redirect" title="Worst-Case">Worst-Case</a>-Effizienz erheblich.

</p>

<div class="mw-heading mw-heading2"><h2 id="Sicherheitsaspekte">Sicherheitsaspekte</h2></div>

<p>Der Einsatz von Datenstrukturen, die entarten können, macht das betreffende Programm anfällig für <a href="Denial_of_Service" title="Denial of Service">Denial-of-Service</a>-Attacken. Dazu kann ein Angreifer das Programm so mit Eingabedaten füttern, dass die internen Datenstrukturen des Programms entarten und das Programm dadurch erheblich mehr Rechenzeit als üblich benötigt – im Extremfall so viel, dass das Programm seinen Zweck nicht mehr erfüllen kann.

</p><p>Als Gegenmaßnahmen wurde in die Hashtabellen der auf vielen Webservern verwendeten Programmiersprache <a href="Perl_(Programmiersprache)" title="Perl (Programmiersprache)">Perl</a> eine Zufallskomponente eingebaut, die bei jedem Programmstart für eine neue interne Verteilung zu speichernder Werte in die Hashtabelle sorgt und einen DoS-Angriff durch absichtliche Entartung damit erheblich erschwert.

</p></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-01-28" href="https://de.wikipedia.org/wiki/?title=Entartung_(Informatik)&oldid=241619855">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>